﻿// 0903train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <cctype>

using namespace std;

/*
 商品中购买 3 件，而且想尽可能的花完资金
 现在请你设计一个程序帮助小明计算尽可能花费的最大资金额

输入
第一行为整型数组 M，数组长度小于100，数组元素记录单个商品的价格；
单个商品价格小于1000；
第二行输入为购买资金的额度R，R < 100000。
输出
输出为满足上述条件的最大花费额度
如果不存在满足上述条件的商品请返回-1

输入
23,26,36,27
78
输出
76
 */
class Solution01
{
public:
    Solution01(vector<int>&num_vec, int limit)
    {
        sort(num_vec.begin(), num_vec.end());

        int result = 0;

        for (int i=0; i<num_vec.size(); i++)
        {
            int remain = limit - num_vec[i];

            int left = i + 1, right = num_vec.size() - 1;
            while (left<right)
            {
                int curr_sum = num_vec[left] + num_vec[right];
	            if (curr_sum>remain)
	            {
		            //下调金额
                    right--;
	            }
                else if (curr_sum<remain)
                {
	                //更新result
                    result = max(result, num_vec[i] + curr_sum);
                    //尝试更大的金额
                    left++;
                }
                else
                {
                    //相等
                    result = limit;
                    break;
                }
                //while (left<right)
            }

        }

        if (result==0)
        {
            cout << -1;
            return;
        }

        cout << result;
        //Solution01
    }
};

/*
 提取最长的数学表达式
 输入
 1-2abcd
 输出
 -1
 */
class Solution02
{
public:
    int computed(string&cal_str)
    {
        //往最后塞一个空格，方便计算最后一个数
        cal_str = cal_str + ' ';

        char pre_sign = '+';

        vector<int>stack_v;
        int curr_num = 0;
        for (auto&cal_ch:cal_str)
        {
            if (isdigit(cal_ch))
            {
                curr_num = curr_num * 10 + cal_ch - '0';
                continue;
            }

            if (pre_sign=='+')
            {
                stack_v.push_back(curr_num);
            }
            else if (pre_sign=='-')
            {
                stack_v.push_back(curr_num*(-1));
            }
            else if (pre_sign=='*')
            {
                int num1 = stack_v.back();
                stack_v.pop_back();

                stack_v.push_back(num1 * curr_num);
            }
            curr_num = 0;
            pre_sign = cal_ch;

        }

        int sum = 0;
        for (auto&num:stack_v)
        {
            sum += num;
        }
        return sum;
    }

    void solve02(string& origin_str)
    {
        //s[i]有3种情况进循环，1数字，2+-号
        int start_index = -1, end_index = -1;

        //前后补2个a, 防止越界
        origin_str = 'a' + origin_str + 'a';
        int s_size = origin_str.size();
        int i = 1;
        while (i < s_size)
        {
            char i_char = origin_str[i];
            if (isdigit(i_char) || i_char == '+' || i_char == '-')
            {
                int j = i;
                while (j < s_size)
                {
                    char j_char = origin_str[j];
                    //j是数字，0需要判断，其他数字合格
                    if (isdigit(j_char))
                    {
                        if (j_char != '0')
                        {
                            j++;
                            continue;
                        }
                        //j_char为0，如果j-1不是数字，j+1是数字，必须终止
                        if (!isdigit(origin_str[j - 1]) && isdigit(origin_str[j + 1]))
                        {
                            j++;
                            break;
                        }
                        //不是前导0合法，继续往前走
                        j++;
                    }
                    else if (j_char == '+' || j_char == '-' || j_char=='*')
                    {
                        //下一位必须是数字
                        if (isdigit(origin_str[j + 1]))
                        {
                            j++;
                            continue;
                        }
                        //否则终止
                        break;
                    }
                    else
                    {
                        break;
                    }
                    //while (j<s_size)
                }

                if (i == j)
                {
                    //防止i不前进，死循环
                    //j主动往前一位，用于给i赋值
                    j++;
                }
                else
                {
                    //更新表达式前后索引
                    if ((j - i) > (end_index - start_index))
                    {
                        start_index = i;
                        end_index = j;
                    }
                }
                i = j;
                continue;
                //if (isdigit(i_char)
            }

            //i不满足情况，往下一个字符
            i++;
        }

        if (start_index == end_index)
        {
            cout << 0;
            return;
        }
        string cal_str = origin_str.substr(start_index, end_index - start_index);
        cout << computed(cal_str);

    }

    Solution02(string&origin_str)
    {
        solve02(origin_str);
        //Solution02
    }
};

/*
 输入描述
10,9,8,7,6,5,4,3,2,1
注：支柱至少有2根，最多10000根，能支持的高度范围1~10^9的整数。柱子的高度是无序的，例子中递减只是巧合。
输出描述
可以支持的最大太阳能板面积：
如：25（10米高支柱和5米高支柱之间）

输入
10,9,8,7,6,5,4,3,2,1
输出
25

25（10米高支柱和5米高支柱之间）
 */
class Solution03
{
public:
    Solution03(vector<int>&num_vec)
    {
        int result = 0;
        for (int i=0; i<num_vec.size();i++)
        {
            int curr_max_right = 0;
            for (int right = num_vec.size()-1; right>i; right--)
            {
                if (num_vec[right]>curr_max_right)
                {
                    int area_h = min(num_vec[right], num_vec[i]);
                    int area_w = right - i;
                    result = max(result, area_w * area_h);
                    curr_max_right = num_vec[right];
                }
            }
        }
        cout << result;
        //Solution03
    }
};

int main()
{
	{
        //vector<int>num_vec = { 10,9,8,7,6,5,4,3,2,1 };
        vector<int>num_vec;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (getline(oh_sstream,token,','))
        {
            num_vec.push_back(stoi(token));
        }

        Solution03 solu(num_vec);
        return 0;
	}
	{
        string num_str;
        getline(cin, num_str);
        //string num_str = "1-2abcd";
        Solution02 solu(num_str);
        //string test_str = "1-2*4";
        //cout << solu.computed(test_str);

        return 0;
	}
/*
23,26,36,27
78
*/
    vector<int>num_vec;
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (getline(oh_sstream, token, ','))
    {
        num_vec.push_back(stoi(token));
    }
    int limit;
    cin >> limit;

    Solution01 solu(num_vec, limit);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
